#include <algorithm>
#include <memory>

template <class T>
class deque {
private:
    // 中控器：指向缓冲区指针数组的二级指针
    T**​ _map;
    size_t _map_size;       // 中控器容量（缓冲区槽位数）
    size_t _buffer_size;    // 每个缓冲区容量（默认512/sizeof(T)）

    // 迭代器结构体（核心）
    struct iterator {
        T* _cur;            // 当前元素指针
        T* _first;          // 当前缓冲区起始位置
        T* _last;           // 当前缓冲区结束位置
        T**​ _node;          // 指向中控器的缓冲区指针条目

        // 运算符重载：跨缓冲区移动[6,7](@ref)
        iterator& operator++() {
            ++_cur;
            if (_cur == _last) {      // 到达缓冲区末尾
                ++_node;             // 跳转至下一缓冲区
                _cur = *_node;       // 重置指针
                _first = _cur;
                _last = _cur + _buffer_size;
            }
            return *this;
        }

        iterator& operator--() {
            if (_cur == _first) {     // 到达缓冲区起始
                --_node;             // 跳转至上一缓冲区
                _cur = *_node + _buffer_size - 1;
                _first = *_node;
                _last = _first + _buffer_size;
            }
            --_cur;
            return *this;
        }

        T& operator*() const { return *_cur; }
    };

    iterator _start;    // 指向第一个有效元素
    iterator _finish;   // 指向最后一个有效元素的下一位

public:
    // 构造函数：初始化中控器和缓冲区[8](@ref)
    deque(size_t num_elements = 0) : _map(nullptr), _map_size(0) {
        _buffer_size = (sizeof(T) <= 512) ? 512 / sizeof(T) : 1;
        _initialize_map(num_elements);
    }

    // 析构函数：释放所有缓冲区和中控器
    ~deque() {
        for (T**​ node = _start._node; node <= _finish._node; ++node)
            delete[] * node;
        delete[] _map;
    }

    // 头部插入（需处理缓冲区不足和中控器扩容）[6](@ref)
    void push_front(const T& value) {
        if (_start._cur != _start._first) {  // 当前缓冲区有空间
            *--_start._cur = value;
        } else {
            _reserve_map_at_front();          // 中控器扩容
            T* new_buffer = new T[_buffer_size];
            _start._node--;                  // 指向新缓冲区
            _start._cur = new_buffer + _buffer_size - 1;
            *_start._cur = value;
            _start._first = new_buffer;
            _start._last = new_buffer + _buffer_size;
        }
    }

    // 尾部插入（逻辑对称）[6](@ref)
    void push_back(const T& value) {
        if (_finish._cur != _finish._last - 1) {
            *(_finish._cur++) = value;
        } else {
            _reserve_map_at_back();
            T* new_buffer = new T[_buffer_size];
            *_finish._node = new_buffer;
            _finish._cur = new_buffer;
            *_finish._cur++ = value;
            _finish._node++;
        }
    }

private:
    // 初始化中控器和缓冲区[8](@ref)
    void _initialize_map(size_t num_elements) {
        size_t num_buffers = num_elements / _buffer_size + 1;
        _map_size = std::max<size_t>(8, num_buffers + 2);
        _map = new T*[_map_size];  // 分配中控器内存

        // 居中预留空间（支持双向扩展）
        T**​ map_start = _map + (_map_size - num_buffers) / 2;
        for (size_t i = 0; i < num_buffers; ++i)
            map_start[i] = new T[_buffer_size];

        // 初始化迭代器指针
        _start._node = map_start;
        _start._cur = map_start[0] + _buffer_size / 2;  // 从中间插入
        _start._first = map_start[0];
        _start._last = map_start[0] + _buffer_size;

        _finish = _start;
    }

    // 中控器扩容（头部）[6](@ref)
    void _reserve_map_at_front() {
        if (_start._node == _map) {  // 中控器头部空间不足
            size_t new_map_size = _map_size * 2;
            T**​ new_map = new T*[new_map_size];
            std::copy(_map, _map + _map_size, new_map + _map_size/2);
            delete[] _map;
            _map = new_map;
            _map_size = new_map_size;
            _start._node += _map_size/2;
            _finish._node += _map_size/2;
        }
    }

    // 中控器扩容（尾部，逻辑对称）[6](@ref)
    void _reserve_map_at_back() { 
        if (_finish._node == _map + _map_size - 1) {
            // 类似_reserve_map_at_front的实现
        }
    }
};